/**************************************************************************************************
	$Header: /pub/cvsroot/mydns/src/mydns/cache.c,v 1.39 2003/03/27 17:28:12 bboy Exp $

	Copyright (C) 2002, 2003  Don Moore <bboy@bboy.net>

	This program is free software; you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation; either version 2 of the License, or
	(at Your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program; if not, write to the Free Software
	Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
**************************************************************************************************/

#include "named.h"

CACHE *DataCache = NULL;							/* Data cache */
CACHE *ReplyCache = NULL;							/* Reply cache */


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	ISPRIME
	Returns 1 if `number' is a prime number, 0 if not.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
static int
isprime(unsigned int number)
{
	register unsigned int div = 3;

	while (div * div < number && number % div != 0)
		div += 2;
	return (number % div != 0);
}
/*--- isprime() ---------------------------------------------------------------------------------*/


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	_CACHE_INIT
	Create, initialize, and return a new CACHE structure.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
static CACHE *
_cache_init(uint32_t limit, uint32_t expire, const char *desc)
{
	CACHE *C;

	if (!(C = calloc(1, sizeof(CACHE))))
		Err("calloc");
	C->limit = limit;
	C->expire = expire;

#if (HASH_TYPE == ORIGINAL_HASH) || (HASH_TYPE == ADDITIVE_HASH)
	/* Make `slots' prime */
	C->slots = limit * CACHE_SLOT_MULTIPLIER;
	C->slots |= 1;
	while (!isprime(C->slots))
		C->slots += 2;
#elif (HASH_TYPE == ROTATING_HASH)
	/* Make `slots' a power of two */
	{
		int		bits;
		uint32_t	slots;

		C->slots = limit * CACHE_SLOT_MULTIPLIER;
		for (slots = C->slots, bits = 0; slots != 1; )
		{
			slots >>= 1;
			bits++;
		}
		if (C->slots & ((1 << bits) - 1))
			bits++;
		slots = 1 << bits;

   	C->slots = slots;
		C->mask = C->slots - 1;
	}
#else
#	error Hash method unknown or unspecified
#endif

	if (!(C->nodes = calloc(C->slots, sizeof(CNODE *))))
		Err("calloc");

#if DEBUG_ENABLED
	Debug("%s cache initialized (%u nodes, %u elements max)", desc, C->slots, limit);
#endif
	return (C);
}
/*--- _cache_init() -----------------------------------------------------------------------------*/


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	CACHE_INIT
	Create the caches used by MyDNS.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void
cache_init(void)
{
	uint32_t	cache_size, zone_cache_size, reply_cache_size;
	int		defaulted;
	int		cache_expire, zone_cache_expire, reply_cache_expire;

	zone_cache_size = atou(conf_get(&Conf, "zone-cache-size", &defaulted));
	if (defaulted)
	{
		cache_size = atou(conf_get(&Conf, "cache-size", NULL));
		zone_cache_size = cache_size - (cache_size / 3);
	}
	zone_cache_expire = atou(conf_get(&Conf, "zone-cache-expire", &defaulted));
	if (defaulted)
		zone_cache_expire = atou(conf_get(&Conf, "cache-expire", NULL));

	reply_cache_size = atou(conf_get(&Conf, "reply-cache-size", &defaulted));
	if (defaulted)
	{
		cache_size = atou(conf_get(&Conf, "cache-size", NULL));
		reply_cache_size = cache_size / 3;
	}
	reply_cache_expire = atou(conf_get(&Conf, "reply-cache-expire", &defaulted));
	if (defaulted)
		reply_cache_expire = atou(conf_get(&Conf, "cache-expire", NULL)) / 2;

	if (zone_cache_size && zone_cache_expire)
		DataCache = _cache_init(zone_cache_size, zone_cache_expire, "data");

	if (reply_cache_size && reply_cache_expire)
		ReplyCache = _cache_init(reply_cache_size, reply_cache_expire, "reply");
}
/*--- cache_init() ------------------------------------------------------------------------------*/


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	CACHE_STATUS
	Called when SIGUSR1 is received, returns a string to append to status.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
char *
cache_status(void)
{
	static char		str[768];
	size_t			zone_cache_size = 0, reply_cache_size = 0;
	register int	ct;
	register CNODE	*n;

	if (!DataCache)
		return ((char *)_("no cache"));

	/* Get the total amount of memory used by the data cache */
	zone_cache_size += sizeof(CACHE);
	zone_cache_size += (sizeof(CNODE *) * DataCache->slots);
	for (ct = 0; ct < (DataCache->slots); ct++)
		for (n = DataCache->nodes[ct]; n; n = n->next_node)
		{
			zone_cache_size += sizeof(CNODE) + n->namelen + 1;
			if (n->data)
			{
				if (n->type == DNS_T_SOA)
					zone_cache_size += mydns_soa_size((MYDNS_SOA *)n->data);
				else
					zone_cache_size += mydns_rr_size((MYDNS_RR *)n->data);
			}
		}

	/* Get the total amount of memory used by the reply cache */
	reply_cache_size += sizeof(CACHE);
	reply_cache_size += (sizeof(CNODE *) * ReplyCache->slots);
	for (ct = 0; ct < (ReplyCache->slots); ct++)
		for (n = ReplyCache->nodes[ct]; n; n = n->next_node)
			zone_cache_size += sizeof(CNODE) + n->namelen + 1 + n->datalen;

	snprintf(str, sizeof(str),
		_("zone cache %.0f%% useful (%u hits, %u misses), %.0f%% full, %u bytes; "
		  "reply cache %.0f%% useful (%u hits, %u misses), %.0f%% full, %u bytes"),
		PCT(DataCache->questions, DataCache->hits), DataCache->hits, DataCache->misses,
		PCT(DataCache->limit, DataCache->count), zone_cache_size,
		PCT(ReplyCache->questions, ReplyCache->hits), ReplyCache->hits, ReplyCache->misses,
		PCT(ReplyCache->limit, ReplyCache->count), reply_cache_size
	);

	return (str);
}
/*--- cache_status() ----------------------------------------------------------------------------*/


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	MRULIST_ADD
	Adds the specified node to the head of the MRU list.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
static void
mrulist_add(CACHE *Cache, CNODE *n)
{
	register CNODE *head = Cache->mru_head;

	if (!n || !Cache) return;

	if (!Cache->mru_head)
	{
		Cache->mru_head = n;
		Cache->mru_head->mru_prev = NULL;
		Cache->mru_head->mru_next = NULL;
		Cache->mru_tail = n;
	}
	else
	{
		n->mru_next = head;
		n->mru_prev = head->mru_prev;
		if (head->mru_prev == NULL)
			Cache->mru_head = n;
		else
			head->mru_prev->mru_next = n;
		head->mru_prev = n;
	}
}
/*--- mrulist_add() -----------------------------------------------------------------------------*/


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	MRULIST_DEL
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
static void
mrulist_del(CACHE *Cache, CNODE *n)
{
	if (!n || !Cache || !Cache->mru_head) return;

	if (n == Cache->mru_head)
	{
		Cache->mru_head = n->mru_next;
		if (Cache->mru_head == NULL)
			Cache->mru_tail = NULL;
		else
			n->mru_next->mru_prev = NULL;
	}
	else
	{
		n->mru_prev->mru_next = n->mru_next;
		if (n->mru_next == NULL)
			Cache->mru_tail = n->mru_prev;
		else
			n->mru_next->mru_prev = n->mru_prev;
	}
}
/*--- mrulist_del() -----------------------------------------------------------------------------*/


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	CACHE_FREE_NODE
	Frees the node specified and removes it from the cache.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
static void
cache_free_node(CACHE *Cache, uint32_t hash, CNODE *n)
{
	register CNODE *prev = NULL, *cur, *next;

	if (!n || hash >= Cache->slots)
		return;

	for (cur = Cache->nodes[hash]; cur; cur = next)
	{
		next = cur->next_node;
		if (cur == n)		/* Delete this node */
		{
			mrulist_del(Cache, n);								/* Remove from MRU/LRU list */

			/* Remove the node */
			if (cur->datalen)
			{
				free(cur->data);
			}
			else if (cur->type == DNS_T_SOA)
			{
				mydns_soa_free((MYDNS_SOA *)cur->data);
			}
			else
			{
				mydns_rr_free((MYDNS_RR *)cur->data);
			}

			if (cur == Cache->nodes[hash])					/* Head of node? */
				Cache->nodes[hash] = cur->next_node;
			else if (prev)
				prev->next_node = cur->next_node;
			free(cur);
			Cache->out++;
			Cache->count--;
			return;
		}
		else
			prev = cur;
	}
	Errx(_("tried to free invalid node %p at %u in cache"), n, hash);
}
/*--- cache_free_node() -------------------------------------------------------------------------*/


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	CACHE_EMPTY
	Deletes all nodes within the cache.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void
cache_empty(CACHE *Cache)
{
	register int ct;
	register CNODE *n, *tmp;

	if (!Cache) return;
	for (ct = 0; ct < Cache->slots; ct++)
		for (n = Cache->nodes[ct]; n; n = tmp)
		{
			tmp = n->next_node;
			cache_free_node(Cache, ct, n);
		}
	Cache->mru_head = Cache->mru_tail = NULL;
}
/*--- cache_empty() -----------------------------------------------------------------------------*/


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	CACHE_CLEANUP
	Deletes all expired nodes within the cache.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void
cache_cleanup(CACHE *Cache)
{
	register int	ct;
	register CNODE	*n, *tmp;

	if (!Cache) return;
	for (ct = 0; ct < Cache->slots; ct++)
		for (n = Cache->nodes[ct]; n; n = tmp)
		{
			tmp = n->next_node;
			if (current_time > n->expire)
			{
				Cache->expired++;
				cache_free_node(Cache, ct, n);
			}
		}
#if DEBUG_ENABLED
	Debug("cache cleanup; %s", cache_status());
#endif
}
/*--- cache_cleanup() ---------------------------------------------------------------------------*/


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	CACHE_HASH
	Returns hash value.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
static inline uint32_t
cache_hash(CACHE *Cache, uint32_t initval, char *name, register size_t namelen)
{
	register uint32_t	hash;
	register char		*p;

	/* Generate hash value */
#if (HASH_TYPE == ORIGINAL_HASH)
	for (hash = initval, p = name; p < name + namelen; p++)
	{
		register int tmp;
		hash = (hash << 4) + (*p);
		if ((tmp = (hash & 0xf0000000)))
		{
			hash = hash ^ (tmp >> 24);
			hash = hash ^ tmp;
		}
	}
	hash %= Cache->slots;
#elif (HASH_TYPE == ADDITIVE_HASH)
	for (hash = initval, p = name; p < name + namelen; p++)
		hash += *p;
	hash %= Cache->slots;
#elif (HASH_TYPE == ROTATING_HASH)
	for (hash = initval, p = name; p < name + namelen; p++)
		hash = (hash << 4) ^ (hash >> 28) ^ (*p);
	hash = (hash ^ (hash>>10) ^ (hash>>20)) & Cache->mask;
#else
#	error Hash method unknown or unspecified
#endif
	return (hash);
}
/*--- cache_hash() ------------------------------------------------------------------------------*/


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	DATA_CACHE_FIND
	Returns the SOA from cache (or via the database if necessary) or NULL if `name' doesn't match.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void *
data_cache_find(uint32_t zone, char *origin, dns_qtype_t type, char *name, size_t namelen)
{
	register uint32_t	hash = 0;
	register CNODE		*n;
	MYDNS_SOA			*soa = NULL;
	MYDNS_RR				*rr = NULL;

	if (!name)
		return (NULL);

	if (DataCache)
	{
		DataCache->questions++;

		hash = cache_hash(DataCache, zone + type, name, namelen);

		/* Look at the appropriate node.  Descend list and find match. */
		for (n = DataCache->nodes[hash]; n; n = n->next_node)
		{
			if ((n->namelen == namelen) && (n->zone == zone) && (n->type == type))
			{
				if (!n->name)
					Errx(_("reply cache node %p at hash %u has NULL name"), n, hash);
				if (!memcmp(n->name, name, namelen))
				{
					if (current_time > n->expire)						/* Node expired */
					{
						cache_free_node(DataCache, hash, n);
						break;
					}
					DataCache->hits++;

					/* Found in cache; move to head of usefulness list */
					mrulist_del(DataCache, n);
					mrulist_add(DataCache, n);
					if (type == DNS_T_SOA)
						return (n->data ? mydns_soa_dup(n->data, 1) : NULL);
					else
						return (n->data ? mydns_rr_dup(n->data, 1) : NULL);
				}
			}
		}
	}

	/* Result not found in cache; Get answer from database */
	if (type == DNS_T_SOA)
	{
		/* Try to load from database */
		if (mydns_soa_load(sql, &soa, name) != 0)
			WarnSQL(sql, "%s: %s", name, _("error loading SOA"));
		if (!soa && namelen > PTR_SUFFIX_LEN && !strcmp(name + (namelen-PTR_SUFFIX_LEN), PTR_SUFFIX))
			if (mydns_soa_make(sql, &soa, name, hostname) != 0)
				Warn("mydns_soa_make(\"%s\", \"%s\"): %s", name, hostname, _("error making SOA"));
		if (!DataCache)
			return ((void *)soa);
	}
	else
	{
		if (mydns_rr_load(sql, &rr, zone, type, name, origin) != 0)
			WarnSQL(sql, _("error finding %s type resource records for name `%s' in zone %u"),
					  mydns_qtype_str(type), name, zone);
		if (!DataCache)
			return ((void *)rr);
	}
	DataCache->misses++;

	/* If the cache is full, delete the least recently used node and add new node */
	if (DataCache->count >= DataCache->limit)
	{
		if (DataCache->mru_tail)
		{
			DataCache->removed++;
			cache_free_node(DataCache, DataCache->mru_tail->hash, DataCache->mru_tail);
		}
		else
			return (type == DNS_T_SOA ? (void *)soa : (void *)rr);
	}

	/* Add to cache */
	DataCache->in++;
	if (!(n = calloc(1, sizeof(CNODE))))
		Err("calloc");
	n->hash = hash;
	n->zone = zone;
	n->type = type;
	strncpy(n->name, name, sizeof(n->name)-1);
	n->namelen = namelen;
	if (type == DNS_T_SOA)
	{
		n->data = mydns_soa_dup(soa, 1);
		n->expire = current_time + ((soa && (soa->ttl < DataCache->expire)) ? soa->ttl : DataCache->expire);
	}
	else
	{
		n->data = mydns_rr_dup(rr, 1);
		n->expire = current_time + ((rr && (rr->ttl < DataCache->expire)) ? rr->ttl : DataCache->expire);
	}
	n->next_node = DataCache->nodes[hash];

	/* Add node to cache */
	DataCache->nodes[hash] = n;
	DataCache->count++;

	/* Add node to head of MRU list */
	mrulist_add(DataCache, n);

	return (type == DNS_T_SOA ? (void *)soa : (void *)rr);
}
/*--- data_cache_find() --------------------------------------------------------------------------*/


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	REPLY_FROM_CACHE
	Attempt to find the reply data whole in the cache.
	Returns nonzero if found, 0 if not found.
	If found, fills in t->reply and t->replylen.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
int
reply_from_cache(TASK *t)
{
	register uint32_t	hash;
	register CNODE		*n;

	if (!ReplyCache)
		return (0);
	if (t->qdlen > DNS_MAXPACKETLEN_UDP)
		return (0);

	hash = cache_hash(ReplyCache, t->qtype, t->qd, t->qdlen);
	ReplyCache->questions++;

	/* Look at the appropriate node.  Descend list and find match. */
	for (n = ReplyCache->nodes[hash]; n; n = n->next_node)
	{
		if ((n->namelen == t->qdlen) && (n->type == t->qtype))
		{
			if (!n->name)
				Errx(_("reply cache node %p at hash %u has NULL name"), n, hash);
			if (!memcmp(n->name, t->qd, t->qdlen))
			{
				if (current_time > n->expire)						/* Node expired */
				{
					cache_free_node(ReplyCache, hash, n);
					break;
				}
				/* Found in cache; move to head of usefulness list */
				mrulist_del(ReplyCache, n);
				mrulist_add(ReplyCache, n);

				/* Fill in task information (t->reply, t->replylen) */
				if (!(t->reply = malloc(n->datalen)))
					Err("malloc");
				memcpy(t->reply, n->data, n->datalen);
				t->replylen = n->datalen;
				ReplyCache->hits++;
				return (1);
			}
		}
	}
	ReplyCache->misses++;
	return (0);
}
/*--- reply_from_cache() ------------------------------------------------------------------------*/


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	ADD_REPLY_TO_CACHE
	Adds the current reply to the reply cache.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void
add_reply_to_cache(TASK *t)
{
	register uint32_t	hash;
	register CNODE		*n;

	if (!ReplyCache)
		return;
	if (t->qdlen > DNS_MAXPACKETLEN_UDP)
		return;

	hash = cache_hash(ReplyCache, t->qtype, t->qd, t->qdlen);

	/* Look at the appropriate node.  Descend list and find match. */
	for (n = ReplyCache->nodes[hash]; n; n = n->next_node)
	{
		if ((n->namelen == t->qdlen) && (n->type == t->qtype))
		{
			if (!n->name)
				Errx(_("reply cache node %p at hash %u has NULL name"), n, hash);

			if (!memcmp(n->name, t->qd, t->qdlen))
			{
				if (current_time > n->expire)						/* Node expired */
				{
					cache_free_node(ReplyCache, hash, n);
					break;
				}
				/* Found in cache; move to head of usefulness list */
				mrulist_del(ReplyCache, n);
				mrulist_add(ReplyCache, n);
				return;
			}
		}
	}

	/* If the cache is full, delete the least recently used node and add new node */
	if (ReplyCache->count >= ReplyCache->limit)
	{
		if (ReplyCache->mru_tail)
		{
			ReplyCache->removed++;
			cache_free_node(ReplyCache, ReplyCache->mru_tail->hash, ReplyCache->mru_tail);
		}
		else
			return;
	}

	/* Add to cache */
	ReplyCache->in++;
	if (!(n = calloc(1, sizeof(CNODE))))
		Err("calloc");
	n->hash = hash;
	n->zone = 0;
	n->type = t->qtype;
	memcpy(n->name, t->qd, t->qdlen);
	n->namelen = t->qdlen;
	if (!(n->data = malloc(t->replylen)))
		Err("malloc");
	memcpy(n->data, t->reply, t->replylen);
	n->datalen = t->replylen;
	n->expire = current_time + ReplyCache->expire;
	n->next_node = ReplyCache->nodes[hash];

	/* Add node to cache */
	ReplyCache->nodes[hash] = n;
	ReplyCache->count++;

	/* Add node to head of MRU list */
	mrulist_add(ReplyCache, n);
}
/*--- add_reply_to_cache() ----------------------------------------------------------------------*/

/* vi:set ts=3: */
/* NEED_PO */
